package array.MinimumSizeSubarray;

/**
 * 题目:给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     注意：
       对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
       如果 s 中存在这样的子串，我们保证它是唯一的答案。
     示例 1：
       输入：s = "ADOBECODEBANC", t = "ABC"
       输出："BANC"

 * 思路:滑动窗口
 * 知识点: 1.ASCII码值是0-127,所以数组128的大小就可以把它包含完毕
 *        2.截取字符串用：s.substring(start, end)
 *        3.toCharArray()可以把字符串转换成char数组
 */
//明天再写一遍
//20250309腾讯一面
//4-23 B站 一面
//4-23 滴滴 二面
public class minSubString {
    public String minWindow(String s, String t) {
        int begin = 0;
        int charTypeCount = 0;//t中不同的字符总类
        int valid = 0; // 当前窗口中满足 t 要求的字符种类数
        int minLen = Integer.MAX_VALUE;//// 最小子串长度
        int minStart = 0; // 新增：记录最小子串的起始位置

        //用toCharArray将String转换为数组
        char[] charArray = s.toCharArray();
        char[] charArray1 = t.toCharArray();

        // 创建字符频率映射数组4
        //为什么采用128大小的数组
        //答:使用128大小的数组（ASCII），所以对于任何字符（0-127）都可以覆盖。
        int[] need = new int[128];
        int[] window = new int[128];

        // 初始化need数组，记录t中每个字符的出现次数
        for (int i = 0; i < charArray1.length; i++) {
            char c = charArray1[i];
            if (need[c] == 0) {
                charTypeCount++;
            }
            need[c]++;
        }

        for (int end = 0; end < charArray.length; end++) {
            char rchar = charArray[end];
            if (need[rchar] > 0) {
                window[rchar]++;
                if (window[rchar] == need[rchar]) {
                    valid++;
                }
            }

            while (valid == charTypeCount) {
                // 记录当前有效窗口的起始位置和长度
                int currentLen = end - begin + 1;
                if (currentLen < minLen) {
                    minLen = currentLen;
                    minStart = begin; // 记录最小子串起始位置
                }

                // 收缩窗口
                char lchar = charArray[begin];
                if (need[lchar] > 0) {
                    window[lchar]--;
                    if (window[lchar] < need[lchar]) {
                        valid--;
                    }
                }
                begin++;
            }
        }

        if (minLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(minStart, minStart + minLen); // 使用记录的起始位置
    }
}

